class Solution {
public:
    void dfs()
    {
        if (cnt > _n)
        {
            ret++;
            return;
        }
        for (int i = 1; i <= _n; i++)
        {
            if (!used[i])
            {
                if (i % cnt == 0 || cnt % i == 0)
                {
                    cnt++;
                    used[i] = true;
                    dfs();

                    cnt--;
                    used[i] = false;
                }
            }
            
        }
    }
    int countArrangement(int n) {
        _n = n;
        dfs();

        return ret;
    }
private:
    int ret = 0;
    int cnt = 1;
    int _n;
    bool used[15] = {false};
};